package com.sunny.l9;


public class Solution {



    public ListNode detectCycle(ListNode head) {


        ListNode cnode = judge(head);

        if(null == cnode)
            return null;

        int len = getLen(cnode);

        return getBeginNode(head, len);

    }

    public ListNode getBeginNode(ListNode head, int len){

        ListNode p1 = head;
        while (len-- > 0){
            p1 = p1.next;
        }
        ListNode p2 = head;
        while (p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;

    }

    public int getLen(ListNode node){

        ListNode p = node.next;

        int len = 1;
        while (null != p){
            if(p == node)
                break;

            p = p.next;
            len++;
        }

        return len;
    }


    public ListNode judge(ListNode head){

        ListNode p1 = head;
        if(null == p1)
            return null;
        ListNode p2 = p1.next;
        if(null == p2)
            return null;

        while (null != p2){

            p1 = p1.next;

            p2 = p2.next;
            if(null == p2)
                return null;
            p2 = p2.next;

            if(p1 == p2)
                return p1;

        }

        return null;

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
 }
